Non-Patent Document 1 discloses an image checking method that utilizes a widely-used feature point arrangement checking method and a widely-used feature point arrangement checking device. Non-Patent Document 1 shows a case where the image checking device is provided for image searching in a document written in English.
Widely-used image checking processing can be divided into two kinds of processing such as registering processing and checking processing. Each of the processing will be described in detail.
In the registering processing, following processing is executed for each of a plurality of images that are registered in advance. First, when one of the registered images is inputted to a registered image feature point extracting module, the centroids of word regions in an English document are extracted as feature points.
Then, combinations of the feature points with the order are computed from the extracted feature points, and an arrangement of a plurality of feature points is computed. Specifically following processing is executed. (A) First, one of the registered images is taken out. (B) Then, one of the plurality of feature points, i.e., a feature point p, is extracted. Then, n-numbers of neighborhood feature points of the feature point p are extracted. (C) Thereafter, m-points are extracted from the n-number of neighboring feature points of the feature point p. (D) Then, a proper single feature point is selected as p0 from the extracted m-points, and the m-points are arranged clockwise by having the feature point p as the center and the feature point p0 as the head to generate a line Lm of the feature points. (E) Subsequently, all lines Lf of the feature points which select f-point are obtained from the line Lm of the feature points by saving the order, and those are arranged in order as in dictionaries. The action of (A) described above is continued for all the registered images, the action of (B) described above is continued until all the feature points are selected as the feature point p, and the action of (C) described above is continued for the combinations of all of the m-number of features points acquired from the n-number of feature points. Therefore, normally, acquired are a great number of lines of the feature points.
Further, an invariant line is computed from the line Lf of the feature points. As shown in FIG. 38, the computed invariant is stored as a feature amount list along with the number (referred to as a registered image number hereinafter) which uniquely designates the registered image and a feature point number (referred to as the feature point number hereinafter) which uniquely, designates the feature point. The stored feature amount list is used for the checking processing that is executed in a latter stage. Non-Patent Document 1 proposes a method which stores the feature amount list by using a hash after executing discretization of the invariant in order to speed up searching. However, this proposal is irrelevant to the present invention, so that explanations thereof are omitted herein.
In the checking processing, first, when a search image is inputted, the centroids of the word regions in the English document are extracted as the feature points.
Then, a combination of the feature points with the order is computed from the extracted feature points, and an arrangement of the feature points is acquired by circulating the combination. Specifically, following processing is executed. (A) First, one of the registered images is taken out. (B) Then, one of the feature points of the registered image is extracted as a feature point p, and n-number of neighborhood feature points of the feature point p are extracted. (C) Thereafter, m-number of feature points are extracted from the n-number of neighborhood feature points of the feature point p. (D) Then, a proper single feature point is selected as p0 from the extracted m-number of feature points, and the m-number of feature points are arranged clockwise by having the feature point p as the center and the feature point p0 as the head to generate a line Lm of the feature points. (E) Subsequently, all lines Lf of the feature points which select f-point are obtained from the line Lm of the feature points by saving the order, and those are arranged in order as in dictionaries. The action of (A) described above is continued for all the search images, the action of (B) described above is continued until all the feature points are selected as the feature point p, the action of (C) described above is continued for the combinations of all of the M-number of feature points acquired from the N-number of feature points, and the action of (D) is continued until all of the m-number of feature points are selected as the feature point p0. Therefore, normally, acquired are a great number of lines of the feature points. This processing is the same processing executed for computing the feature point arrangement in the registering processing except that the action of (D) described above is continued until all of the m-number of feature points are selected as the feature point p0.
Further, an invariant line is computed from the line Lf of the feature points. The computed invariant line is collated with the invariant line in the feature amount list stored in the registering processing. When it is found as a result of the collation that the invariant lines match with each other, a coincident number (vote number) for the registered image number in the feature amount list is incremented (voted) by 1. Non-Patent Document 1 proposes other processing for preventing mis-corresponding of invariant lines. However, that proposes is irrelevant to the present invention, so that explanations thereof are omitted herein.
At last, the scores of each registered image are computed from the coincident number for each registered image (vote number acquired from the result voted for each registered image) by using a following computing equation, and the registered image having the maximum score is outputted as the checking result.S(di)=V(di)−cN(di)Note here that di is the registered image number, V(di) is the number of votes for the registered image whose registered image number is di, N(di) is the number of feature points contained in the registered image whose registered image number is di, and c is a proportionality constant of the feature point number and the mis-vote defined in a preparatory experiment.
The value of f when executing the registering processing and the checking processing varies depending on the types of transformation tolerated between the registered image and the search image. Non-Patent Document 1 proposes a method which uses an affine invariant computed from f=4 points to allow the affine invariant between the registered image and the search image, for example. When there is an arbitrary affine transformation between two images, the affine invariant is characterized to take a same value from a combination of corresponding points. Therefore, even if there is a change in the shapes due to the arbitrary affine transformation generated between the registered image and the search image, the lines of the invariants computed respectively from the feature point arrangement acquired from the registered image and the feature point arrangement acquired from the corresponding search image becomes the same theoretically through conducting collation by using the feature amounts acquired with the affine invariants. As a result, the feature point checking device that uses the affine invariant as the invariant and the image checking device that uses the feature point checking device can conduct highly precise checking, when it is considered that the transformation between the registered image and the search image can be expressed with the affine transformation.
Further Patent Document 1 discloses a method which checks a single registered image with a plurality of images that are inputted in time series.    Non-Patent Document 1: Tomohiro NAKAI, et al., “Use of Affine Invariants and Similarity Invariants in Fast Camera-based Document Image Retrieval”, Technical Report of IEICE (Pattern Recognition/Media Understanding, PRMU-184-201), Feb. 16, 2006, pp. 25-30    Patent Document 1: Japanese Unexamined Patent Publication 2006-309718